Search for: All records

Abstract For a subset$$A$$of an abelian group$$G$$, given its size$$|A|$$, its doubling$$\kappa =|A+A|/|A|$$, and a parameter$$s$$which is small compared to$$|A|$$, we study the size of the largest sumset$$A+A'$$that can be guaranteed for a subset$$A'$$of$$A$$of size at most$$s$$. We show that a subset$$A'\subseteq A$$of size at most$$s$$can be found so that$$|A+A'| = \Omega (\!\min\! (\kappa ^{1/3},s)|A|)$$. Thus, a sumset significantly larger than the Cauchy–Davenport bound can be guaranteed by a bounded size subset assuming that the doubling$$\kappa$$is large. Building up on the same ideas, we resolve a conjecture of Bollobás, Leader and Tiba that for subsets$$A,B$$of$$\mathbb{F}_p$$of size at most$$\alpha p$$for an appropriate constant$$\alpha \gt 0$$, one only needs three elements$$b_1,b_2,b_3\in B$$to guarantee$$|A+\{b_1,b_2,b_3\}|\ge |A|+|B|-1$$. Allowing the use of larger subsets$$A'$$, we show that for sets$$A$$of bounded doubling, one only needs a subset$$A'$$with$$o(|A|)$$elements to guarantee that$$A+A'=A+A$$. We also address another conjecture and a question raised by Bollobás, Leader and Tiba on high-dimensional analogues and sets whose sumset cannot be saturated by a bounded size subset. 

We develop a quantitative large deviations theory for random hypergraphs, which rests on tensor decomposition and counting lemmas under a novel family of cut-type norms. As our main application, we obtain sharp asymptotics for joint upper and lower tails of homomorphism counts in the r-uniform Erdo ̋s–Rényi hypergraph for any fixed r≥2, generalizing and improving on previous results for the Erdo ̋s–Rényi graph (r=2). The theory is sufficiently quantitative to allow the density of the hypergraph to vanish at a polynomial rate, and additionally yields tail asymptotics for other nonlinear functionals, such as induced homomorphism counts.